{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find and Replace Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findAndReplacePattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找和替换模式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个单词列表&nbsp;<code>words</code>&nbsp;和一个模式&nbsp;&nbsp;<code>pattern</code>，你想知道 <code>words</code> 中的哪些单词与模式匹配。</p>\n",
    "\n",
    "<p>如果存在字母的排列 <code>p</code>&nbsp;，使得将模式中的每个字母 <code>x</code> 替换为 <code>p(x)</code> 之后，我们就得到了所需的单词，那么单词与模式是匹配的。</p>\n",
    "\n",
    "<p><em>（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）</em></p>\n",
    "\n",
    "<p>返回 <code>words</code> 中与给定模式匹配的单词列表。</p>\n",
    "\n",
    "<p>你可以按任何顺序返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;abc&quot;,&quot;deq&quot;,&quot;mee&quot;,&quot;aqq&quot;,&quot;dkd&quot;,&quot;ccc&quot;], pattern = &quot;abb&quot;\n",
    "<strong>输出：</strong>[&quot;mee&quot;,&quot;aqq&quot;]\n",
    "<strong>解释：\n",
    "</strong>&quot;mee&quot; 与模式匹配，因为存在排列 {a -&gt; m, b -&gt; e, ...}。\n",
    "&quot;ccc&quot; 与模式不匹配，因为 {a -&gt; c, b -&gt; c, ...} 不是排列。\n",
    "因为 a 和 b 映射到同一个字母。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= pattern.length = words[i].length&nbsp;&lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-and-replace-pattern](https://leetcode.cn/problems/find-and-replace-pattern/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-and-replace-pattern](https://leetcode.cn/problems/find-and-replace-pattern/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abc\",\"deq\",\"mee\",\"aqq\",\"dkd\",\"ccc\"]\\n\"abb\"', '[\"a\",\"b\",\"c\"]\\n\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(words,pattern):\n",
    "            mp = {}\n",
    "            for x,y in zip(words,pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                else:\n",
    "                    if mp[x] != y:\n",
    "                        return False\n",
    "            return True\n",
    "        return [word for word in words if match(word,pattern) and match(pattern,word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "\n",
    "        def match(s) -> bool: \n",
    "            ab, ba = dict(), dict()\n",
    "\n",
    "            for w, p in zip(s, pattern): \n",
    "\n",
    "                if w in ab or p in ba: \n",
    "                    if ab.get(w, p) != p or ba.get(p, w) != w:\n",
    "                        return False \n",
    "                \n",
    "                else:\n",
    "                    ab[w] = p\n",
    "                    ba[p] = w\n",
    "            \n",
    "            return True \n",
    "        \n",
    "        return [word for word in words if match(word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            d = dict()\n",
    "            for a, b in zip(w, pattern):\n",
    "                if a not in d:\n",
    "                    if b in d.values():\n",
    "                        break\n",
    "                    d[a] = b\n",
    "                elif d[a] != b:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            d = dict()\n",
    "            for k, v in zip(word, pattern):\n",
    "                if k not in d:\n",
    "                    if v in d.values():\n",
    "                        break\n",
    "                    d[k] = v\n",
    "                elif d[k] != v:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        result = []\n",
    "        for word in words:\n",
    "            mapping = collections.defaultdict(set)\n",
    "            reverse_mapping = collections.defaultdict(set)\n",
    "            for i in range(len(word)):\n",
    "                mapping[pattern[i]].add(word[i])\n",
    "                reverse_mapping[word[i]].add(pattern[i])\n",
    "            flag = True\n",
    "            for key in mapping:\n",
    "                if len(mapping[key]) > 1:\n",
    "                    flag = False\n",
    "                    break\n",
    "            for key in reverse_mapping:\n",
    "                if len(reverse_mapping[key]) > 1:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                result.append(word)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for s in words:\n",
    "            change = {}\n",
    "            use_char = {}\n",
    "            do = True\n",
    "            for i in range(len(pattern)):\n",
    "                if pattern[i] not in change.keys():\n",
    "                    if s[i] not in use_char.keys():\n",
    "                        change[pattern[i]] = s[i]\n",
    "                        use_char[s[i]] = True\n",
    "                    else:\n",
    "                        do = False\n",
    "                        break\n",
    "                    \n",
    "                elif change[pattern[i]]!=s[i]:\n",
    "                    do = False\n",
    "                    break\n",
    "                \n",
    "            if do:\n",
    "                res.append(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: \n",
    "        result=[]\n",
    "        l=len(pattern)\n",
    "        for i in words:\n",
    "            dic={}\n",
    "            for j in range(l):\n",
    "                if pattern[j] not in dic:\n",
    "                    if i[j] not in dic.values():\n",
    "                        dic[pattern[j]]=i[j]\n",
    "                    else:break\n",
    "                elif i[j]!=dic[pattern[j]]:\n",
    "                    break\n",
    "            else:\n",
    "                result.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word, pattern):\n",
    "            hashMap = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in hashMap:\n",
    "                    hashMap[x] = y\n",
    "                elif hashMap[x] != y:\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if len(word) == len(pattern):\n",
    "                cur1, cur2 = {}, {}\n",
    "                i = 0\n",
    "                while i < len(pattern):\n",
    "                    if pattern[i] not in cur1 and word[i] not in cur2:\n",
    "                        cur1[pattern[i]] = word[i]\n",
    "                        cur2[word[i]] = pattern[i]\n",
    "                    elif pattern[i] in cur1 and cur1[pattern[i]] != word[i] or word[i] in cur2 and cur2[word[i]] != pattern[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(pattern):\n",
    "                    res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word: str, pattern: str) -> bool:\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:  # word 中的同一字母必须映射到 pattern 中的同一字母上\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: \n",
    "        result=[]\n",
    "        l=len(pattern)\n",
    "        for i in words:\n",
    "            dic={}\n",
    "            for j in range(l):\n",
    "                if pattern[j] not in dic:\n",
    "                    if i[j] not in dic.values():\n",
    "                        dic[pattern[j]]=i[j]\n",
    "                    else:break\n",
    "                elif i[j]!=dic[pattern[j]]:\n",
    "                    break\n",
    "            else:\n",
    "                result.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        n = len(pattern)\n",
    "        for word in words:\n",
    "            word2pattern = dict()\n",
    "            pattern2word = dict()\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if word[i] not in word2pattern and pattern[i] not in pattern2word:\n",
    "                    word2pattern[word[i]] = pattern[i]\n",
    "                    pattern2word[pattern[i]] = word[i]\n",
    "                elif word[i] not in word2pattern or pattern[i] not in pattern2word:\n",
    "                    flag = False\n",
    "                    break\n",
    "                elif word2pattern[word[i]] != pattern[i] or pattern2word[pattern[i]] != word[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans.append(word)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word, pattern):\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pat: str) -> List[str]:\n",
    "        return [s for s in words if len(set(s)) == len(set(pat)) == len(set(zip(s, pat)))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word: str, pattern: str) -> bool:\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:  # word 中的同一字母必须映射到 pattern 中的同一字母上\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def judge(word,pattern):\n",
    "            d = {}\n",
    "            dr = {}\n",
    "            for i in range(len(word)):\n",
    "                if pattern[i] not in d and word[i] not in dr:\n",
    "                    d[pattern[i]] = word[i]\n",
    "                    dr[word[i]] = pattern[i]\n",
    "                elif pattern[i] not in d:\n",
    "                    return False\n",
    "                else:\n",
    "                    if d[pattern[i]] != word[i]:\n",
    "                        return False\n",
    "            return True\n",
    "        result = []\n",
    "        for word in words:\n",
    "            if judge(word,pattern):\n",
    "                result.append(word)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        for i in words:\n",
    "            if len(set(i)) != len(set(pattern)):\n",
    "                continue\n",
    "            else :\n",
    "                mydict,flag = {},True\n",
    "                for j in range(len(pattern)):\n",
    "                    if pattern[j] not in mydict.keys():\n",
    "                        mydict[pattern[j]] = i[j]\n",
    "                    else :\n",
    "                        if mydict[pattern[j]] != i[j]:\n",
    "                            flag = False\n",
    "                            break\n",
    "                if flag :\n",
    "                    ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word: str, pattern: str) -> bool:\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:  # word 中的同一字母必须映射到 pattern 中的同一字母上\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkMatched(self, word, pattern):\n",
    "        if len(word) != len(pattern):\n",
    "            return false\n",
    "\n",
    "        m = {}\n",
    "        n = {}\n",
    "        l = len(word)\n",
    "        for i in range(l):\n",
    "            if not m.get(word[i]):\n",
    "                m[word[i]] = pattern[i]\n",
    "            else:\n",
    "                if m[word[i]] != pattern[i]:\n",
    "                    return False\n",
    "\n",
    "\n",
    "        for i in range(l):\n",
    "            if not n.get(pattern[i]):\n",
    "                n[pattern[i]] = word[i]\n",
    "            else:\n",
    "                if n[pattern[i]] != word[i]:\n",
    "                    return False\n",
    "        return True\n",
    "                    \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        if len(words) == 0:\n",
    "            return []\n",
    "\n",
    "        ret = []\n",
    "        for word in words:\n",
    "            if self.checkMatched(word, pattern):\n",
    "                ret.append(word)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/find-and-replace-pattern/\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def check(word, pattern):\n",
    "            m = {pattern[0]: word[0]}\n",
    "            mc, wc = Counter(pattern), Counter(word)\n",
    "            for i in range(1, len(pattern)):\n",
    "                p = pattern[i]\n",
    "                if p not in m.keys():\n",
    "                    m[p] = word[i]\n",
    "                else:\n",
    "                    if m[p] != word[i]:\n",
    "                        return False\n",
    "            # print(word, m, mc, wc)\n",
    "            for k, v in m.items():\n",
    "                rk = m[k]\n",
    "                if mc[k] != wc[rk]:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            if check(word, pattern):\n",
    "                ans.append(word)\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        {'words': [\"abc\",\"deq\",\"mee\",\"aqq\",\"dkd\",\"ccc\"], 'pattern': 'abb'},\n",
    "    ]:\n",
    "        ret = s.findAndReplacePattern(testcase['words'], testcase['pattern'])\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            d = dict()\n",
    "            for k, v in zip(word, pattern):\n",
    "                if k not in d:\n",
    "                    if v in d.values():\n",
    "                        break\n",
    "                    d[k] = v\n",
    "                elif d[k] != v:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        # 字典映射\n",
    "        hashp = {itemp:i for (i, itemp) in enumerate(pattern)}\n",
    "        #print(hashp)\n",
    "        result = []\n",
    "        for word in words:\n",
    "            hashw = {itemw:j for (j, itemw) in enumerate(word)}\n",
    "            #print(hashw)\n",
    "            if list(hashp.values()) == list(hashw.values()):  # 利用字典有序特性\n",
    "                result.append(word)\n",
    "        return result\n",
    "\n",
    "        # 双射\n",
    "        def match(word: str, pattern: str) -> bool:\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:  # word 中的同一字母必须映射到 pattern 中的同一字母上\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]\n",
    "\n",
    "        # 双射 字典+哈希\n",
    "        n = len(pattern)\n",
    "        res = []\n",
    "        for word in words:\n",
    "            dic = defaultdict(str)\n",
    "            st = set()\n",
    "            for i in range(n):\n",
    "                if not dic[word[i]]:\n",
    "                    if pattern[i] not in st:\n",
    "                        dic[word[i]] = pattern[i]\n",
    "                        st.add(pattern[i])\n",
    "                    else: \n",
    "                        break\n",
    "                elif dic[word[i]] != pattern[i]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(word)\n",
    "        return res\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            a,b = dict(),dict()\n",
    "            flag = True\n",
    "            for x,y in zip(w,pattern):\n",
    "                if x not in a and y not in b:\n",
    "                    a[x] = y\n",
    "                    b[y] = x\n",
    "                elif x in a and y == a[x]:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag: ans.append(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def f(s1, s2):\n",
    "            lst = set((c1, c2) for c1, c2 in zip(s1, s2)) \n",
    "            lst1 = list(zip(*lst))\n",
    "            #print(s1, s2, lst, set(lst1[0]), set(lst1[1]))\n",
    "            return len(set(lst1[0])) == len(set(lst1[1])) == len(lst)\n",
    "        #f(\"mee\", \"abb\")\n",
    "        #f(\"abb\", \"abb\")\n",
    "        #f(\"abc\", \"abd\")\n",
    "        #f(\"abc\", \"abb\")\n",
    "        #f(\"ccc\", \"abb\")\n",
    "        return [w for w in words if f(w, pattern)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def match(self,w,p):\r\n",
    "        d = {}\r\n",
    "        for i in range(len(w)):\r\n",
    "            if w[i] not in d:\r\n",
    "                if p[i] in d.values():\r\n",
    "                    return False\r\n",
    "                d[w[i]] = p[i]\r\n",
    "            elif d[w[i]] != p[i]:\r\n",
    "                return False\r\n",
    "        return True\r\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\r\n",
    "        return [w for w in words if self.match(w,pattern)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        # 双射\n",
    "        def match(word: str, pattern: str) -> bool:\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:  # word 中的同一字母必须映射到 pattern 中的同一字母上\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]\n",
    "\n",
    "        # 双射 字典+哈希\n",
    "        n = len(pattern)\n",
    "        res = []\n",
    "        for word in words:\n",
    "            dic = defaultdict(str)\n",
    "            st = set()\n",
    "            for i in range(n):\n",
    "                if not dic[word[i]]:\n",
    "                    if pattern[i] not in st:\n",
    "                        dic[word[i]] = pattern[i]\n",
    "                        st.add(pattern[i])\n",
    "                    else: \n",
    "                        break\n",
    "                elif dic[word[i]] != pattern[i]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(word)\n",
    "        return res\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        result = []\n",
    "        for word in words:\n",
    "            pattern_to_word = {}\n",
    "            word_to_pattern = {}\n",
    "            i = 0\n",
    "            while i < len(pattern):\n",
    "                if pattern[i] not in pattern_to_word:\n",
    "                    pattern_to_word[pattern[i]] = word[i]\n",
    "                elif pattern_to_word[pattern[i]] != word[i]:\n",
    "                    break\n",
    "                if word[i] not in word_to_pattern:\n",
    "                    word_to_pattern[word[i]] = pattern[i]\n",
    "                elif word_to_pattern[word[i]] != pattern[i]:\n",
    "                    break\n",
    "                i += 1\n",
    "            if i == len(pattern):\n",
    "                result.append(word)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        l = len(set(pattern))\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            if len(dict(zip(word,pattern)))==l and len(set(zip(word,pattern)))==l:\n",
    "                ans.append(word)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\r\n",
    "        def getmodel(word):\r\n",
    "            d = dict()\r\n",
    "            w = list()\r\n",
    "            for i, alpha in enumerate(word):\r\n",
    "                if alpha not in d.keys():\r\n",
    "                    d[alpha] = i\r\n",
    "                w.append(d[alpha])\r\n",
    "            return w\r\n",
    "        \r\n",
    "        model = getmodel(pattern)\r\n",
    "        ans = list()\r\n",
    "        for word in words:\r\n",
    "            if getmodel(word) == model:\r\n",
    "                ans.append(word)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def isPatten(s1,s2):\n",
    "            dic = {}\n",
    "            dic2 = {}\n",
    "            for idx in range(len(s1)):\n",
    "                if s1[idx] not in dic:\n",
    "                    dic[s1[idx]] = s2[idx]\n",
    "                elif dic[s1[idx]] != s2[idx]:\n",
    "                    return False\n",
    "            for idx in range(len(s1)):\n",
    "                if s2[idx] not in dic2:\n",
    "                    dic2[s2[idx]] = s1[idx]\n",
    "                elif dic2[s2[idx]] != s1[idx]:\n",
    "                    return False\n",
    "           \n",
    "            return True\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            if isPatten(word,pattern):\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        result = []\n",
    "        def get_pattern(s):\n",
    "            map = {}\n",
    "            res = []\n",
    "            count = 0\n",
    "            for c in s:\n",
    "                if c not in map:\n",
    "                    map[c] = count\n",
    "                    count += 1\n",
    "                res.append(map[c])\n",
    "            return tuple(res)\n",
    "        \n",
    "        pattern_repr = get_pattern(pattern)\n",
    "        for word in words:\n",
    "            if get_pattern(word) == pattern_repr:\n",
    "                result.append(word)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        \n",
    "        def check(st):\n",
    "            n = len(st)\n",
    "            pre = dict()\n",
    "            for i in range(n):\n",
    "                if st[i] in pre and pre[st[i]] != pattern[i]:\n",
    "                    return False\n",
    "                pre[st[i]] = pattern[i]\n",
    "            return max(Counter(pre.values()).values()) == 1\n",
    "        \n",
    "        return [word for word in words if check(word)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if self.func(word, pattern):\n",
    "                res.append(word)\n",
    "        return res\n",
    "    def func(self, word: str, pattern: str):\n",
    "        for k, v in enumerate(pattern):\n",
    "            if pattern.index(v) != word.index(word[k]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        sp=\"\"\n",
    "        dp=defaultdict(int)\n",
    "        temp='a'\n",
    "        ans=[]\n",
    "        for c in pattern:\n",
    "            if dp[c]<1:\n",
    "                dp[c]=ord(temp)\n",
    "                sp+=temp\n",
    "                temp=chr(ord(temp)+1)\n",
    "            else :\n",
    "                sp+=chr(dp[c])\n",
    "        for word in words:\n",
    "            dw=defaultdict(int)\n",
    "            sw=\"\"\n",
    "            tempw='a'\n",
    "            for c in word:\n",
    "                if dw[c]<1:\n",
    "                    dw[c]=ord(tempw)\n",
    "                    sw+=tempw\n",
    "                    tempw=chr(ord(tempw)+1)\n",
    "                else :\n",
    "                    sw+=chr(dw[c])\n",
    "            if sw==sp:\n",
    "                ans.append(word)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def check(word,pattern):\n",
    "            if len(word)!=len(pattern):\n",
    "                return False\n",
    "            for i in range(len(word)):\n",
    "                if word.index(word[i])!=pattern.index(pattern[i]):\n",
    "                    return False\n",
    "            return True\n",
    "        res=[]\n",
    "        for i in range(len(words)):\n",
    "            if check(words[i],pattern):\n",
    "                res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            hashmap = {}\n",
    "            hashmap1 = {}\n",
    "            Flag = True\n",
    "            for i,j in zip(word,pattern):\n",
    "                if j in hashmap:\n",
    "                    if hashmap[j] != i:\n",
    "                        Flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    hashmap[j] = i\n",
    "                if i in hashmap1:\n",
    "                    if  hashmap1[i] != j:\n",
    "                        Flag = False\n",
    "                else:\n",
    "                    hashmap1[i] = j\n",
    "            if Flag:\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        n = 0\n",
    "        ans = []\n",
    "        for i in pattern:\n",
    "            if not i.isdigit():\n",
    "                pattern = pattern.replace(i, str(n))\n",
    "                n += 1\n",
    "        for w in words:\n",
    "            t = w\n",
    "            n = 0\n",
    "            for i in w:\n",
    "                if not i.isdigit():\n",
    "                    w = w.replace(i, str(n))\n",
    "                    n += 1\n",
    "            if w == pattern:\n",
    "                ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def mapping(pp, ss):\n",
    "            d, used = {}, set()\n",
    "            for p, s in zip(pp, ss):\n",
    "                if p in d:\n",
    "                    if d[p] != s:\n",
    "                        return False\n",
    "                else:\n",
    "                    if s in used:\n",
    "                        return False\n",
    "                    d[p] = s\n",
    "                    used.add(s)\n",
    "            return True\n",
    "        \n",
    "        return [word for word in words if mapping(pattern, word)]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        answer_list = list()\n",
    "        for word in words:\n",
    "            if check(pattern, word):\n",
    "                answer_list.append(word)\n",
    "        return answer_list\n",
    "    \n",
    "def check(pattern, word):\n",
    "    word_pattern_dict, pattern_word_dict = dict(), dict()\n",
    "    for w_letter, p_letter in zip(word, pattern):\n",
    "        if (w_letter in word_pattern_dict and word_pattern_dict[w_letter] != p_letter) or p_letter in pattern_word_dict and pattern_word_dict[p_letter] != w_letter:\n",
    "            return False \n",
    "        else:\n",
    "            word_pattern_dict[w_letter] = p_letter\n",
    "            pattern_word_dict[p_letter] = w_letter\n",
    "    return True \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        l1 = []\n",
    "        mode = get_model(pattern)\n",
    "        for i in words:\n",
    "            if len(i) == len(pattern):\n",
    "                if get_model(i) == mode:\n",
    "                    l1.append(i)\n",
    "        return l1\n",
    "def get_model(pattern):\n",
    "    dict1 = {}\n",
    "    mode = []\n",
    "    for (i,j) in enumerate(pattern):\n",
    "        if j not in dict1:\n",
    "            dict1[j] = i\n",
    "        mode.append(dict1[j])\n",
    "    return mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word, pattern):\n",
    "            mp = {}\n",
    "            for x, y in zip(word, pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word, pattern) and match(pattern, word)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "\n",
    "        rs = []\n",
    "        for word in words:\n",
    "            d1 = {}\n",
    "            d2 = {}\n",
    "            flag = True\n",
    "            for c1, c2 in zip(word, pattern):\n",
    "                if c1 in d1:\n",
    "                    if d1[c1] != c2:\n",
    "                        flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    d1[c1] = c2\n",
    "                if c2 in d2:\n",
    "                    if d2[c2] != c1:\n",
    "                        flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    d2[c2] = c1\n",
    "            \n",
    "            if flag:\n",
    "                rs.append(word)\n",
    "        return rs\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def fuc(s: str, t: str, n: int) -> bool:\n",
    "            s_t = {}\n",
    "            t_s = {}\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                c1 = s[i]\n",
    "                c2 = t[i]\n",
    "                a = s_t.get(c1)\n",
    "                b = t_s.get(c2)\n",
    "                if a != None and b != None:\n",
    "                    if a != c2 or b !=c1:\n",
    "                        return False\n",
    "                elif a == None and b == None:\n",
    "                    s_t[c1] = c2\n",
    "                    t_s[c2] = c1\n",
    "                else:\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "        ans = []\n",
    "        n = len(pattern)\n",
    "        for word in words:\n",
    "            if fuc(word,pattern,n):\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        sp=\"\"\n",
    "        dp=defaultdict(int)\n",
    "        temp='a'\n",
    "        ans=[]\n",
    "        for c in pattern:\n",
    "            if dp[c]<1:\n",
    "                dp[c]=ord(temp)\n",
    "                sp+=str(temp)\n",
    "                temp=chr(ord(temp)+1)\n",
    "            else :\n",
    "                sp+=str(chr(dp[c]))\n",
    "        for word in words:\n",
    "            dw=defaultdict(int)\n",
    "            sw=\"\"\n",
    "            tempw='a'\n",
    "            for c in word:\n",
    "                if dw[c]<1:\n",
    "                    dw[c]=ord(tempw)\n",
    "                    sw+=str(tempw)\n",
    "                    tempw=chr(ord(tempw)+1)\n",
    "                else :\n",
    "                    sw+=str(chr(dw[c]))\n",
    "            if sw==sp:\n",
    "                ans.append(word)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        result = []\n",
    "        for i in range(len(words)):\n",
    "            dicrpattern1 = collections.defaultdict()\n",
    "            tmp = 0\n",
    "            for j in range(len(pattern)):\n",
    "                if words[i][j] + \"1\" in dicrpattern1:\n",
    "                    if pattern[j] + \"2\" == dicrpattern1[words[i][j] + \"1\"] :\n",
    "                        tmp = tmp + 1\n",
    "                else:\n",
    "                    tmp1 = 0\n",
    "                    for k , v in dicrpattern1.items():\n",
    "                        if v != pattern[j] + \"2\":\n",
    "                            # print(v , pattern[j] + \"2\")\n",
    "                            tmp1 = tmp1 + 1\n",
    "                    if tmp1 == len(dicrpattern1):\n",
    "                        dicrpattern1[words[i][j] + \"1\"] = pattern[j] + \"2\"\n",
    "                        tmp = tmp + 1\n",
    "            if tmp == len(pattern):\n",
    "                result.append(words[i])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def check(a,b):\n",
    "            B=collections.defaultdict(str)\n",
    "            C=collections.defaultdict(str)\n",
    "            for i in range(len(a)):\n",
    "                if (a[i] in B and B[a[i]]!=b[i]) or (b[i] in C and C[b[i]]!=a[i]):\n",
    "                    return False\n",
    "                else:\n",
    "                    B[a[i]]=b[i]\n",
    "                    C[b[i]]=a[i]\n",
    "            return True\n",
    "        ans=[]\n",
    "        for each in words:\n",
    "            if check(each,pattern):\n",
    "                ans.append(each)\n",
    "        return ans\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(a,b):\n",
    "            dic = {}\n",
    "            for x,y in zip(a,b):\n",
    "                if x not in dic:\n",
    "                    dic[x] = y\n",
    "                elif x in dic and dic[x] != y:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if match(word,pattern) and match(pattern,word):\n",
    "                res.append(word)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if len(word) == len(pattern):\n",
    "                cur1, cur2 = {}, {}\n",
    "                i = 0\n",
    "                while i < len(pattern):  \n",
    "                    if pattern[i] in cur1 and cur1[pattern[i]]!=word[i] or word[i] in cur2 and cur2[word[i]]!=pattern[i]:\n",
    "                        break\n",
    "                    cur1[pattern[i]] = word[i]\n",
    "                    cur2[word[i]] = pattern[i]\n",
    "                    i += 1\n",
    "                if i == len(pattern):\n",
    "                    res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        # 双向映射\n",
    "        def match(w1, w2):\n",
    "            map1 = {}\n",
    "            map2 = {}\n",
    "            n = len(w1)\n",
    "            if n != len(w2):\n",
    "                return False\n",
    "            flag1 = True\n",
    "            flag2 = True\n",
    "            for i in range(n):\n",
    "                if w1[i] not in map1:  \n",
    "                    # 第一次出现时确定映射关系，后面再碰到时验证映射关系\n",
    "                    map1[w1[i]] = w2[i] \n",
    "                elif map1[w1[i]] != w2[i]:\n",
    "                    flag1 = False\n",
    "                if w2[i] not in map2:\n",
    "                    map2[w2[i]] = w1[i]\n",
    "                elif map2[w2[i]] != w1[i]:\n",
    "                    flag2 = False\n",
    "            return flag1 and flag2\n",
    "        \n",
    "        return [w for w in words if match(w, pattern)]    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\r\n",
    "        n = len(pattern)\r\n",
    "        ans = list()\r\n",
    "        for word in words:\r\n",
    "            map1, map2 = dict(), dict()\r\n",
    "            add = 1\r\n",
    "            for i in range(n):\r\n",
    "                if word[i] not in map1.keys():\r\n",
    "                    map1[word[i]] = pattern[i]\r\n",
    "                elif map1[word[i]] != pattern[i]:\r\n",
    "                    add = 0\r\n",
    "                    break\r\n",
    "                if pattern[i] not in map2.keys():\r\n",
    "                    map2[pattern[i]] = word[i]\r\n",
    "                elif map2[pattern[i]] != word[i]:\r\n",
    "                    add = 0\r\n",
    "                    break\r\n",
    "            if add: ans.append(word)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:   \n",
    "\n",
    "\n",
    "        def check(a, b):\n",
    "            a2b = {}\n",
    "            b2a = {}\n",
    "            for i in range(len(a)):\n",
    "                if a[i] not in a2b:\n",
    "                    a2b[a[i]] = b[i]\n",
    "                    if b[i] not in b2a:\n",
    "                        b2a[b[i]] = a[i]\n",
    "                    else:\n",
    "                        if b2a[b[i]] != a[i]:\n",
    "                            return False\n",
    "                else:\n",
    "                    if a2b[a[i]] != b[i]:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if check(w, pattern):\n",
    "                res.append(w)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res_words = []\n",
    "        for word in words:\n",
    "            flag = True\n",
    "            dct = {}\n",
    "            for idx, i in enumerate(word):\n",
    "                if pattern[idx] not in dct:\n",
    "                    dct[pattern[idx]] = i\n",
    "                else:\n",
    "                    if i != dct[pattern[idx]]:\n",
    "                        flag = False\n",
    "                        break\n",
    "            if len(dct) != len(set(dct.values())): flag = False\n",
    "            if flag: res_words.append(word)\n",
    "        return res_words\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def f(s1, s2):\n",
    "            lst = set((c1, c2) for c1, c2 in zip(s1, s2)) \n",
    "            lst1 = list(zip(*lst))\n",
    "            #print(s1, s2, lst, set(lst1[0]), set(lst1[1]))\n",
    "            return len(set(lst1[0])) == len(set(lst1[1])) == len(lst)\n",
    "        #f(\"mee\", \"abb\")\n",
    "        #f(\"abb\", \"abb\")\n",
    "        #f(\"abc\", \"abd\")\n",
    "        #f(\"abc\", \"abb\")\n",
    "        #f(\"ccc\", \"abb\")\n",
    "        return [w for w in words if f(w, pattern)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ischeck(self,word:str,pattern:str)->bool:\n",
    "        hashmap={}\n",
    "        for w,p in zip(word,pattern):\n",
    "            if w not in hashmap:\n",
    "                hashmap[w]=p\n",
    "            elif hashmap[w]!=p:\n",
    "                return False\n",
    "        return True\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res=[]\n",
    "        for word in words:\n",
    "            if(self.ischeck(word,pattern) and self.ischeck(pattern,word)):\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            dic = {}\n",
    "            for a, b in zip(pattern, word):\n",
    "                if a not in dic:\n",
    "                    if b not in dic.values():\n",
    "                        dic[a] = b\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    if b != dic[a]:\n",
    "                        break\n",
    "            else:\n",
    "                res.append(word)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def check(x):\n",
    "            dict1=dict()\n",
    "            seen=set()\n",
    "            for i,j in enumerate(pattern):\n",
    "                if j not in dict1 and x[i] not in seen:\n",
    "                    dict1[j]=x[i]\n",
    "                    seen.add(x[i])\n",
    "                elif j not in dict1 and x[i] in seen:\n",
    "                    return False\n",
    "                elif j in dict1:\n",
    "                    if dict1[j]!=x[i]:\n",
    "                        return False\n",
    "            return True\n",
    "        ans=[]\n",
    "        for i in words:\n",
    "            if check(i):\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def str2base(s: str) -> List[int]:\n",
    "            d = defaultdict(int)\n",
    "            for x in s:\n",
    "                d[x] += 1\n",
    "            t = [x[0] for x in sorted(list(d.items()), key = lambda x: -x[1])]\n",
    "            \n",
    "            d = defaultdict(str)\n",
    "            for i in range(len(t)):\n",
    "                d[t[i]] = str(ord('a') + i)\n",
    "            a = [d[x] for x in s]\n",
    "\n",
    "            return a\n",
    "        \n",
    "        p = str2base(pattern)\n",
    "        a = []\n",
    "        for w in words:\n",
    "            if str2base(w) == p:\n",
    "                a.append(w)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:\n",
    "        def match(word,pattern):\n",
    "            mp = {}\n",
    "            for x,y in zip(word,pattern):\n",
    "                if x not in mp:\n",
    "                    mp[x] = y\n",
    "                elif mp[x] != y:\n",
    "                    return False\n",
    "            return True\n",
    "        return [word for word in words if match(word,pattern) and match(pattern,word)]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
